package com.github.yangyishe.p200;

import java.util.Arrays;

/**
 * 130. 被围绕的区域
 * https://leetcode.cn/problems/surrounded-regions/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
 * 输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
 * 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
 * 示例 2：
 *
 * 输入：board = [["X"]]
 * 输出：[["X"]]
 *
 *
 * 提示：
 *
 * m == board.length
 * n == board[i].length
 * 1 <= m, n <= 200
 * board[i][j] 为 'X' 或 'O'
 */
public class Problem130 {
    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'X','X','X','X'},
                {'X','O','O','X'},
                {'X','X','O','X'},
                {'X','O','X','X'}
        };

        Problem130 problem130 = new Problem130();
        problem130.solve(board);

        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));
        }
    }

    /**
     * 思路:
     * 标记处理法
     *
     * 1. 创建一个标记地图,和board一样大小,记录是否标记过
     * 2. 从边界位置出发, 递归+回溯找'O'. 找到即标记. 直到将所有与边界相连的区域均标记
     * 3. 遍历原地图, 如果是'O',则找标记地图, 看是否标记过. 如果已标记, 则不处理; 否则标记为'X'
     *
     * @param board
     */
    public void solve(char[][] board) {
        int height=board.length;
        int width=board[0].length;
        boolean[][] markBoard=new boolean[height][width];
        for(int i=0;i<width;i++){
            searchBoundaryO(board,markBoard,0,i);
            searchBoundaryO(board,markBoard,height-1,i);
        }
        for(int row=1;row<height-1;row++){
            searchBoundaryO(board,markBoard,row,0);
            searchBoundaryO(board,markBoard,row,width-1);
        }

        for(int row=0;row<height;row++){
            for(int col=0;col<width;col++){
                if(markBoard[row][col]){
                    continue;
                }
                if(board[row][col]=='O'){
                    board[row][col]='X';
                }
            }
        }

    }

    private void searchBoundaryO(char[][] board,boolean[][] markBoard,int row,int col){
        int height=board.length;
        int width=board[0].length;
        if(row<0||row>=height){
            return;
        }
        if(col<0||col>=width){
            return;
        }
        if(markBoard[row][col]){
            return;
        }
        markBoard[row][col]=true;
        if(board[row][col]=='X'){
            return;
        }
        searchBoundaryO(board,markBoard,row,col+1);
        searchBoundaryO(board,markBoard,row+1,col);
        searchBoundaryO(board,markBoard,row,col-1);
        searchBoundaryO(board,markBoard,row-1,col);

    }
}
